﻿#include <iostream>
#include <vector>
using namespace std;


class Solution
{
    vector<int> tmp;
public:
    // 912. 排序数组
    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int l, int r)
    {
        if (l >= r)
            return;

        int mid = (r - l) / 2 + l;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];

        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= r)
            tmp[i++] = nums[cur2++];

        for (int i = l; i <= r; i++)
            nums[i] = tmp[i - l];
    }
};

int main()
{

    return 0;
}